#include <algorithm>
#include <iostream>
#include <chrono>
#include <format>
#include <random>
#include <set>
#include <unordered_set>
using namespace std;

mt19937 rnd(time(0));

void benchmark(const string &name, const auto &func) {
  auto start = std::chrono::high_resolution_clock::now();
  func();
  auto end = std::chrono::high_resolution_clock::now();
  auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
  cout << format("{} execution time: {} ms\n", name, duration.count());
}
/**
 *                   set  unordered_set
 * insert/emplace O(logn)  O(1)
 * erase          O(logn)  O(1)
 * find           O(logn)  O(1)
 * []             O(logn)  O(1)
 */
int main() {
  int n = 1000000;
  set<int> s;
  unordered_set<int> us;
  vector<int> vec;
  benchmark("vec push", [&]() {
    for (int i = 0; i < n; i ++) {
      vec.push_back(rnd());
    }
  });
  benchmark("set insert", [&]() { // nlogn
    for (int i = 0; i < n; i ++) {
      s.insert(vec[i]);
    }
  });
  benchmark("unordered set insert", [&]() {  // O(n) * C
    for (int i = 0; i < n; i ++) {
      us.insert(vec[i]);
    }
  });

  vector<int> targets(1000000);
  for (auto &x : targets) x = rnd();
  vector<int> ans1, ans2, ans3;
  // benchmark("vec find", [&]() {
  //   for (int target : targets) {
  //     for (int i = 0; i < n; i ++) {
  //       if (vec[i] == target) {
  //         ans1.push_back(target);
  //         break;
  //       }
  //     }
  //   }
  // });
  benchmark("set find", [&]() { // O(logn)
    for (int target : targets) {
      if (s.find(target) != s.end()) {
        ans2.push_back(target);
      }
    }
  });
  benchmark("unordered set find", [&]() {  // O(1)  C
    for (int target : targets) {
      if (us.count(target)) {
        ans3.push_back(target);
      }
    }
  });
  // for (size_t i = 0; i < ans1.size(); i ++) {
  //   if (ans1[i] != ans2[i]  || ans1[i] != ans3[i]) {
  //     cout << "error" << endl;
  //   }
  // }
}